'''
树的叶子节点,不能再分的
树的度,看最多的叉
满二叉树: 每一层的结点都达到最大值
完全二叉树:  叶子结点只能出现在最下层和次下层,并且最下层的结点都集中在该层的最左边的若干位置
二叉树的存储方式: 链式,顺序
顺序二叉树:[9,8,7,6,5,0,1,2,4,3]
父节点 i 左节点2i+1 右节点2i+2

堆是完全二叉树 , 大根堆(任何一个结点都比其孩子结点大),小根堆
大根堆,排序后为增序
堆的向下调整性质

构造堆:农村包围城市,从下层向上
挨个出数:领导退休
'''

#时间复杂度O(logn)
def sift(li, low, high):
    '''
    :param li: 列表
    :param low: 堆的根节点位置
    :param high: 堆的最后一个元素的位置
    :return:
    '''
    i = low  # i指向根节点
    j = 2 * i + 1  # 左孩子
    tmp = li[low]  # 堆顶存起来
    while j <= high:  # 只要j位置有数
        if j + 1 <= high and li[j + 1] > li[j]:  # 如果右孩子大
            j = j + 1  # 指向右孩子
        if li[j] > tmp:
            li[i] = li[j]
            i = j  # 往下一层
            j = i * 2 + 1
        else:  # tmp更大,把tmp放到i的位置上
            break
    li[i] = tmp  # tmp放到叶子节点上


# 建堆
def heap_sort(li):
    n = len(li)
    for i in range((n - 2) // 2, -1, -1):
        # i 代表建堆的时候调整的根
        sift(li, i, n - 1)
    # 建堆完成,然后挨个出数
    for i in range(n - 1, -1, -1):
        # i 指向当前堆的最后一个
        li[0], li[i] = li[i], li[0]
        sift(li, 0, i - 1)  # i-1是新的high


li = [i for i in range(100)]
import random
random.shuffle(li)
print(li)

heap_sort(li)
print(li)

